// 将数组和减半的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/
public class MinimumOperationsToHalveArraySum {

    public static void main(String[] args) {
        int[] nums = {5,19,8,1};
        System.out.println(halveArray(nums));
    }

    public static int MAX = 100001;
    public static long[] heap = new long [MAX];

    public static int size;
    public static int halveArray(int[] nums) {
        size = nums.length;
        long sum = 0;

        for(int i = size - 1; i >= 0; i--) {
            heap[i] = (long) nums[i] << 20;  //将nums中的每个数扩到2的20次方放入heap数组中
            sum += heap[i]; //求和
            heapfy(i);     //建大堆
        }
        sum /= 2; //减少一半的数

        int count = 0;
        for(long minus = 0; minus < sum; count++) {
            long cur = heap[0]/2;
            minus += cur;
            heap[0] = cur;
            heapfy(0);
        }

        return count;
    }

    //向下调整建大堆
    public static void heapfy(int parent) {
        int child = parent * 2 + 1;
        while (child < size) {
            child = child + 1 < size && heap[child+1] > heap[child] ? child + 1 : child;
            if(heap[child] > heap[parent]) {
                swap(child,parent);
            }
            else {
                break;
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }

    public static void swap(int i, int j) {
        long temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

}
